{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# 1. LinkedList Summary" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "LinkedList's are a data structure to hold a variable amount of data. Array's are O(1) (constant time) to access an element, where LinkedList are O(n) where n is the length of the list.\n", "\n", "*For more information on Big-O notation, see page 80 of your textbook.*\n", "\n", "When we have a Recursive Data Structure, it makes sense to have a Recursive method to go along with it." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1.1 Node" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "* Node instances hold the data, and a link to next Node\n", "* They contain definitions of length(), and append()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 1.2 LinkedList" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "* This is an instance to hold the start of the chain of nodes (called `head`)\n", "* Makes it so that there is something when the list is empty\n", "* also has methds length() and append(), but will call the head's version, if there is a head" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 2. Problem!" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Consider the following definition of another linked list idea." ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "| Added class List\n", "\n" ] } ], "source": [ "class List {\n", " double car;\n", " List cdr;\n", " \n", " List(double value) {\n", " car = value;\n", " }\n", "}" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "| Added variable list of type List with initial value List@44e81672\n", "\n" ] } ], "source": [ "List list = new List(23);" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "| Expression value is: 23.0\n", "| assigned to temporary variable $3 of type double\n", "\n" ] }, { "data": { "text/plain": [ "23.0" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "list.car" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "| Expression value is: null\n", "| assigned to temporary variable $4 of type List\n", "\n" ] }, { "data": { "text/plain": [ "null" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "list.cdr" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "| Added method cons(double,List)\n", "\n" ] } ], "source": [ "List cons(double value, List list) {\n", " List retval = new List(value);\n", " retval.cdr = list;\n", " return retval;\n", "}" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "| Variable list has been assigned the value List@5fe5c6f\n", "\n" ] } ], "source": [ "list = cons(67, list);" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "| Expression value is: 67.0\n", "| assigned to temporary variable $8 of type double\n", "\n" ] }, { "data": { "text/plain": [ "67.0" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "list.car" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "| Expression value is: 23.0\n", "| assigned to temporary variable $7 of type double\n", "\n" ] }, { "data": { "text/plain": [ "23.0" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "list.cdr.car" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 2.1 Now let's make some long lists!" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n" ] } ], "source": [ "import java.lang.Math;" ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "| Expression value is: 0.3753894908396601\n", "| assigned to temporary variable $9 of type double\n", "\n" ] }, { "data": { "text/plain": [ "0.3753894908396601" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "Math.random()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "What is in the Math library?\n", "\n", "http://docs.oracle.com/javase/8/docs/api/java/lang/Math.html" ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n" ] } ], "source": [ "for (int i=0; i < 100; i++) {\n", " list = cons(Math.random(), list);\n", "}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now, let's check to see how long this list is:" ] }, { "cell_type": "code", "execution_count": 12, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "| Added method length(List)\n", "\n" ] } ], "source": [ "int length(List list) {\n", " if (list == null) {\n", " return 0;\n", " } else if (list.cdr == null) {\n", " return 1;\n", " } else {\n", " return 1 + length(list.cdr);\n", " }\n", "}" ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "| Expression value is: 0\n", "| assigned to temporary variable $12 of type int\n", "\n" ] }, { "data": { "text/plain": [ "0" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "length(null)" ] }, { "cell_type": "code", "execution_count": 14, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "| Expression value is: 102\n", "| assigned to temporary variable $13 of type int\n", "\n" ] }, { "data": { "text/plain": [ "102" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "length(list)" ] }, { "cell_type": "code", "execution_count": 15, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n" ] } ], "source": [ "for (int i=0; i < 10000; i++) {\n", " list = cons(Math.random(), list);\n", "}" ] }, { "cell_type": "code", "execution_count": 16, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "| Expression value is: 10102\n", "| assigned to temporary variable $15 of type int\n", "\n" ] }, { "data": { "text/plain": [ "10102" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "length(list)" ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n" ] } ], "source": [ "for (int i=0; i < 100000; i++) {\n", " list = cons(Math.random(), list);\n", "}" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": false }, "outputs": [], "source": [ "length(list)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "```\n", "| java.lang.StackOverflowError thrown\n", "| at length (#23:7)\n", "| at length (#23:7)\n", "| at length (#23:7)\n", "| at length (#23:7)\n", "| at length (#23:7)\n", "```" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 2.2 What happened?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "When Java calls a function, the current place for the return value is put on a \"stack\" so that it knows what to do with it when the answer is computed.\n", "\n", "A stack is a data structure that we will explore. Basically, it is like a stack of plates in the dinning hall: first one in is the last one out.\n", "\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We will explore a stack soon, but for now we need to realize that using recursion in Java can have this bad side-effect.\n", "\n", "So, let's write length without recursion:" ] }, { "cell_type": "code", "execution_count": 20, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "| Modified method length(List)\n", "| Update overwrote method length(List)\n", "\n" ] } ], "source": [ "int length(List list) {\n", " int count = 0;\n", " while (list != null) {\n", " list = list.cdr;\n", " count++;\n", " }\n", " return count;\n", "}\n" ] }, { "cell_type": "code", "execution_count": 21, "metadata": { "collapsed": false }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "| Expression value is: 110102\n", "| assigned to temporary variable $20 of type int\n", "\n" ] }, { "data": { "text/plain": [ "110102" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "length(list)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# 3. Summary" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Recursive data structures in Java are fine.\n", "\n", "Recursive processing in Java is not so fine.\n", "\n", "Because Java doesn't handle recursive processing very well, we will avoid it for potentially large problems. Recursive processing is a beautify, wonderful tool, but doesn't play well with Java." ] } ], "metadata": { "kernelspec": { "display_name": "Java 9", "language": "java", "name": "java9" }, "language_info": { "file_extension": ".class", "mimetype": "application/java-vm", "name": "java" } }, "nbformat": 4, "nbformat_minor": 0 }